<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"
            "http://www.w3.org/TR/REC-html40/loose.dtd">
<HTML>
<HEAD>



<META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<META name="GENERATOR" content="hevea 1.08">
<LINK rel="stylesheet" type="text/css" href="tutorial.css">
<TITLE>
Introduction
</TITLE>
</HEAD>
<BODY >
<A HREF="tutorial115.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial117.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
<HR>

<H2 CLASS="section"><A NAME="htoc226">16.1</A>&nbsp;&nbsp;Introduction</H2><UL>
<LI><A HREF="tutorial116.html#toc112">What is Mathematical Programming?</A>
<LI><A HREF="tutorial116.html#toc113">Why interface to Mathematical Programming solvers?</A>
<LI><A HREF="tutorial116.html#toc114">Example formulation of an MP Problem</A>
</UL>

The eplex library allows an external Mathematical Programming solver to be
used by ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP>. It is designed to allow the external solver to be seen
as another solver for ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP>, possibly in co-operation with
the existing `native' solvers of ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP> such as the <I>ic</I> solver. It is
not specific to a given external solver, with the differences between
different solvers (largely) hidden from the user, so that the user can
write the same code and it will run on the different solvers.<BR>
<BR>
The exact types of problems that can be solved (and methods to solve them)
are solver dependent, but currently linear programming, mixed integer
programming and quadratic programming problems can be solved.<BR>
<BR>
The rest of this chapter is organised as follows: the remainder of this
introduction gives a very brief description of Mathematical Programming, which
can be skipped if the reader is familiar with the concepts. 
Section&nbsp;<A HREF="tutorial118.html#mpmodelling">16.3</A> demonstrates the modelling of an MP problem, and the
following section discusses some of the more advanced features of the library
that are useful for hybrid techniques.<BR>
<BR>
<A NAME="toc112"></A>
<H3 CLASS="subsection"><A NAME="htoc227">16.1.1</A>&nbsp;&nbsp;What is Mathematical Programming?</H3>
<A NAME="whatmp"></A>
<A NAME="@default405"></A>
<A NAME="@default406"></A>
<A NAME="@default407"></A>
<A NAME="@default408"></A>
<A NAME="@default409"></A>
Mathematical Programming (MP) (also known as numerical optimisation) is the study of optimisation using
mathematical/numerical techniques. A problem is modelled
by a set of simultaneous equations: an
objective function that is to be minimised or maximised, subject to a set of
constraints on the problem variables, expressed as equalities and
inequalities. <BR>
<BR>
Many subclasses of MP problems have found important practical
applications. In particular, Linear Programming (LP)
problems and Mixed Integer Programming (MIP) problems are perhaps the most
important. LP problems have both a linear objective function and linear
constraints. MIP problems are LP problems where some or all of the
variables are constrained to take on only integer values. <BR>
<BR>
It is beyond the scope of this chapter to cover MP in
any more detail. However, for most usages of the eplex library, the user
need not know the details of MP &ndash; it can be treated as a black-box
solver.
<DL CLASS="description" COMPACT=compact><DT CLASS="dt-description">
<B>&#8857;</B><DD CLASS="dd-description"> <FONT COLOR="#9832CC">For more information on Mathematical Programming, you can read a
textbook on the subject such as H.&nbsp;P.&nbsp;Williams' <I>Model Building in
Mathematical Programming</I> [</FONT><A HREF="tutorial133.html#Williams99"><CITE><FONT COLOR="#9832CC">30</FONT></CITE></A><FONT COLOR="#9832CC">].</FONT>
</DL>


	<BLOCKQUOTE CLASS="figure"><DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV>
	<DIV CLASS="center">
	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#DB9370">
	
<UL CLASS="itemize"><LI CLASS="li-itemize">
Linear Programming (LP) problems: linear constraints and objective
function, continuous variables.
<LI CLASS="li-itemize">Mixed Integer Programming (MIP) problems: LP problems with some or
all variables restricted to taking integral values.
</UL>

	</TD>
</TR></TABLE>
	</DIV>
	<BR>
<BR>
<DIV CLASS="center">Figure 16.1: Classification of MP problems</DIV><BR>
<BR>

	<DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV></BLOCKQUOTE>
<A NAME="toc113"></A>
<H3 CLASS="subsection"><A NAME="htoc228">16.1.2</A>&nbsp;&nbsp;Why interface to Mathematical Programming solvers?</H3>
<A NAME="whymp"></A>
Much research effort has been devoted to developing efficient ways of
solving the various subclasses of MP problems for over 50 years. The
external solvers are state-of-the-art implementations of some of these
techniques. The eplex library allows the user to model an MP problem in
ECLiPSe, and then solve the problem using the best available MP tools.<BR>
<BR>
In addition, the eplex library allows for the user to write programs that
combines MP's global algorithmic solving techniques with the local
propagation techniques of Constraint Logic
Programming. <BR>
<BR>
<A NAME="toc114"></A>
<H3 CLASS="subsection"><A NAME="htoc229">16.1.3</A>&nbsp;&nbsp;Example formulation of an MP Problem</H3> 
<BLOCKQUOTE CLASS="figure"><DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV>
<DIV CLASS="center">
<IMG SRC="tutorial043.gif">
</DIV>
<BR>
<BR>
<DIV CLASS="center">Figure 16.2: An Example MP Problem</DIV><BR>
<BR>

<A NAME="tpprob"></A>
<DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV></BLOCKQUOTE>
Figure&nbsp;<A HREF="#tpprob">16.2</A> shows an example of an MP problem.
It is a transportation problem where 
several plants (1-3) have varying product producing capacities that must
be transported to various clients (A-D), each requiring various amounts of
the product. The per-unit cost of transporting the product to
the clients also varies. The problem is to minimise the transportation
cost whilst satisfying the demands of the clients. <BR>
<BR>
To formulate the problem, we define the amount of product transported from
a plant <I>N</I> to a client <I>p</I> as the variable <I>Np</I>, e.g. <I>A</I>1
represents the cost of transporting to plant <I>A</I> from client 1. There are
two kinds of constraints:
<UL CLASS="itemize"><LI CLASS="li-itemize">
The amount of product delivered from all the plants to a client must be equal to the
client's demand, e.g. for client A, which can recieve products from plants
1-3:  <I>A</I>1 + <I>A</I>2 + <I>A</I>3 = 21 <BR>
<BR>
<LI CLASS="li-itemize">The amount of product sent by a plant must not be more than its
capacity, e.g. for plant 1, which can send products to plants A-D:
<I>A</I>1 + <I>B</I>1 + <I>C</I>1 + <I>D</I>1 &#8804; 50 </UL>
The objective is to minimise the transportation cost, thus the objective
function is to minimise the combined costs of transporting the product to
all 4 clients from the 3 plants.<BR>
<BR>
Putting everything
together, we have the following formulation of the problem:<BR>
<BR>
Objective function:
<DIV CLASS="center">
min(10<I>A</I>1 + 7<I>A</I>2 + 200<I>A</I>3 + 8<I>B</I>1 + 5<I>B</I>2 + 10<I>B</I>3 + 5<I>C</I>1 + 5<I>C</I>2 + 8<I>C</I>3 + 9<I>D</I>1 + 3<I>D</I>2 + 7<I>D</I>3) 
</DIV>
<BR>
<BR>
Constraints:<BR>
<BR>
<DIV CLASS="center"><TABLE CELLSPACING=2 CELLPADDING=0>
<TR><TD ALIGN=right NOWRAP><I>A</I>1 + <I>A</I>2 + <I>A</I>3</TD>
<TD ALIGN=center NOWRAP>=</TD>
<TD ALIGN=left NOWRAP>21</TD>
</TR>
<TR><TD ALIGN=right NOWRAP><I>B</I>1 + <I>B</I>2 + <I>B</I>3</TD>
<TD ALIGN=center NOWRAP>=</TD>
<TD ALIGN=left NOWRAP>40</TD>
</TR>
<TR><TD ALIGN=right NOWRAP><I>C</I>1 + <I>C</I>2 + <I>C</I>3</TD>
<TD ALIGN=center NOWRAP>=</TD>
<TD ALIGN=left NOWRAP>34</TD>
</TR>
<TR><TD ALIGN=right NOWRAP><I>D</I>1 + <I>D</I>2 + <I>D</I>3</TD>
<TD ALIGN=center NOWRAP>=</TD>
<TD ALIGN=left NOWRAP>10</TD>
</TR>
<TR><TD ALIGN=right NOWRAP><I>A</I>1 + <I>B</I>1 + <I>C</I>1 + <I>D</I>1</TD>
<TD ALIGN=center NOWRAP>&#8804;</TD>
<TD ALIGN=left NOWRAP>50</TD>
</TR>
<TR><TD ALIGN=right NOWRAP><I>A</I>2 + <I>B</I>2 + <I>C</I>2 + <I>D</I>2</TD>
<TD ALIGN=center NOWRAP>&#8804;</TD>
<TD ALIGN=left NOWRAP>30</TD>
</TR>
<TR><TD ALIGN=right NOWRAP><I>A</I>3 + <I>B</I>3 + <I>C</I>3 + <I>D</I>3</TD>
<TD ALIGN=center NOWRAP>&#8804;</TD>
<TD ALIGN=left NOWRAP>40</TD>
</TR></TABLE></DIV><BR>
<BR>
<HR>
<A HREF="tutorial115.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial117.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
</BODY>
</HTML>
